package models.re.aaa;

/* AAA algorithm
 * @author: Lu Yao
 *
 */

import java.util.*;

import models.aaa.Asset;
import models.re.IData;
import models.re.IRelation;
import models.re.ISimilarity;
import models.re.realData.AssetRank;
import models.re.realData.RealData;
import models.re.simulatedData.SimulatedDataOne;
import models.spider.stats.Stopwatch;

import org.jgrapht.graph.*;

import play.db.jpa.JPA;

import scala.concurrent.Await;
import scala.concurrent.Future;
import scala.concurrent.duration.Duration;

import akka.actor.ActorRef;
import akka.actor.ActorSystem;
import akka.actor.Props;
import akka.actor.UntypedActor;
import akka.actor.UntypedActorFactory;
import akka.pattern.Patterns;
import akka.routing.RoundRobinRouter;
import akka.util.Timeout;

/*  TO DO LIST 
 * ---parameter should be able to change:
 * relations
 * relation weights
 * personal factor
 * iteration number
 */

public class AAAAlgorithm {
	//private static volatile IData data = null;
	//private static String[] ALL_NODES = null;
	private static String[] ALL_RELATIONS = { "belong", "similar" };
	private static int RELATION_NUMBER = ALL_RELATIONS.length;
	private static double[] relation_weights = { 1.0, 0.0 };
	//private static int NODES_NUMBER = 0;
	private static int[] EMPTY_ACTION = new int[RELATION_NUMBER];
	//private static ArrayList<String> ARRAY_NODES = new ArrayList<String>();
	
	
	
	///////////////////////////////////////////////////////////////////
	
	
	public static void parallelCompute(final int threads) {
		//IData data = new RealData();
		Stopwatch totalTime = new Stopwatch();
		
		ActorSystem system = ActorSystem.create("ComputeAAASystem");
		ActorRef master = system.actorOf(new Props(new UntypedActorFactory() {
				private static final long serialVersionUID = 1L;
				public UntypedActor create() {
					return new Master(threads);
				}
			}), "master");
		
		Timeout timeout = new Timeout(Duration.create(1, java.util.concurrent.TimeUnit.HOURS));
		Future<Object> future = Patterns.ask(master, new End(),timeout);
		try {
			Await.result(future,timeout.duration());
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		totalTime.stop();
		System.out.println("Whole ranking in " + totalTime.elapsed() + "ms");
	}
	
	private static class Master extends UntypedActor {
		
		private ActorRef router=null;
		private ActorRef master=null;
		private int count = 0;
		private Boolean end = false;
		String[] FULLDATA = null;
		
		public Master(int threads) {
			this.router = this.getContext().actorOf(new Props(Worker.class).withRouter(new RoundRobinRouter(threads)),"workerRouter");
			final IData data = new RealData();					
			JPA.withTransaction(new play.libs.F.Callback0() {
                @Override
                public void invoke() throws Throwable {
                	AssetRank.purge();
                }
            });
			JPA.withTransaction(new play.libs.F.Callback0() {
                @Override
                public void invoke() throws Throwable {
                	loadFULLDATA(data);
                }
            });
			for (int j = 0; j < FULLDATA.length; j++) {
				router.tell(new Add(FULLDATA[j],data),getSelf());
				count++;
			}
		}
		
		private void loadFULLDATA(IData data) {
			FULLDATA = data.getAllNodesIds().toArray(new String[data.getAllNodesIds().size()]);
		}
		
		@Override
		public void onReceive(Object message) throws Exception {
			// TODO Auto-generated method stub
			if (message instanceof Add) {
				router.tell(message, getSelf());		
				count++;				
			} 
			else if(message instanceof Computed) {
				count--;
				System.out.println(count);
				if(count==0 && end) master.tell(new End(),getSelf());
			}
			else if(message instanceof End) {
				end = true;
				this.master=getSender();
				if(count==0 && end) master.tell(new End(),getSelf());
			}
			else {
				unhandled(message);
			}
		}
		
	}
	
	// Worker for the parallel similarities computing
	private static class Worker extends UntypedActor {

		@Override
		public void onReceive(final Object message) throws Exception {
			// TODO Auto-generated method stub
			if (message instanceof Add) {
				final Add add = (Add) message;
				JPA.withTransaction(new play.libs.F.Callback0() {
	                @Override
	                public void invoke() throws Throwable {
	                	compute(add.getTarget(),add.getData());
	                }	              
	            });
				getSender().tell(new Computed(),getSelf());
			}
			else {
				unhandled(message);
			}
		}
		
	}
	
	// Messages for the parallel similarities computing
	private static final class Add {

        protected String target = null;        
        protected IData data = null;

		Add(final String target, final IData data) {
            this.target = target;
            this.data = data;
        }

        public String getTarget() {
            return target;
        }
        
        public IData getData() {
        	return data;
        }
    }
	
	private static class Computed {}	
	private static class End {}
	
	
	@SuppressWarnings("unchecked")
	private static void compute(String target, IData data) {
		// TODO Auto-generated method stub
		SubGraph neis = new SubGraph(data);
		System.out.println("Compute ranks for item "+target);
		
		if(Asset.find.byId(Long.decode(target)).getType()!=Asset.Type.ASSET) {
			ArrayList<String> ARRAY_NODES = neis.GetNeighbors(target);
			// System.out.println(" nodes array: "+ARRAY_NODES);
			String[] ALL_NODES = (String[]) ARRAY_NODES.toArray(new String[ARRAY_NODES.size()]);
			// ALL_NODES = data.getAllNodesIds().toArray(new
			// String[data.getAllNodesIds().size()]);
			// System.out.println("all nodes: " + ALL_NODES
			// +"\n node set size: " +
			// NODES_NUMBER);
			// for(int i=0; i<NODES_NUMBER;i++){
			// ARRAY_NODES.add(ALL_NODES[i]);
			//
			// }
			//
			for (int i = 0; i < RELATION_NUMBER; i++) {
				EMPTY_ACTION[i] = 0;
			}
			DirectedWeightedMultigraph<String, DefaultWeightedEdge>[] graphArray;
			graphArray = new DirectedWeightedMultigraph[RELATION_NUMBER];
			Stopwatch wg = new Stopwatch();
			graphArray = GraphConstruct(target,data,ARRAY_NODES);
			wg.stop();
			System.out.println("graph construct used " + wg.elapsed() + "ms");

			for (int relation = 0; relation < RELATION_NUMBER; relation++) {
				System.out.println(ALL_RELATIONS[relation]
						+ " vertices number "
						+ graphArray[relation].vertexSet().size()
						+ "  edges number "
						+ graphArray[relation].edgeSet().size());
			}

			Stopwatch wpg = new Stopwatch();
			double damping = 0.35, personal = 0.6;

			NodeScore pageranks = PageRank(graphArray, damping, personal,
					target, 0.000001, 5, ALL_NODES);
			System.out.println("length = " + pageranks.size());
			wpg.stop();
			System.out.println("page rank used " + wpg.elapsed() + "ms");

			// ********** pageranks = pageranks.sortByScore();
			TreeMap<String,Double> sortedPageranks = pageranks.sortByScore();
			// ********** pageranks.delete(target, and all other assets
			// connected with target in belong)
			ArrayList<String> toRemove = new ArrayList<String>();
			toRemove.add(target);
			if(graphArray[0].containsVertex(target)) {
				for(DefaultWeightedEdge edge : graphArray[0].edgesOf(target)) {
					String linked = graphArray[0].getEdgeSource(edge);
					if(!linked.equals(target)) toRemove.add(linked);
					else toRemove.add(graphArray[0].getEdgeTarget(edge));
				}
			}
			for(String remove : toRemove) sortedPageranks.remove(remove);
			// if pagerank.size < 10, pagerank.add(10-pagerank.size similar items)
			if(sortedPageranks.size()<10)
				for(ISimilarity sim: data.Similarity(Long.decode(target), 10-sortedPageranks.size())) 
					sortedPageranks.put(sim.getTarget().getStrId(),0.0);
			
			// ********** save pagerank top 10 in database
			int i = 0;
			for(String rank: sortedPageranks.keySet()) {
				data.CReateRank(Long.decode(target), Long.decode(rank), sortedPageranks.get(rank));
				i++;
				if(i==10) break;
			}
			
		}
		else {
			// **** else, if it is an asset, find top 10 similar entities.
			ArrayList<String> similarities = new ArrayList<String>();
			similarities = neis.GetNeighborSimi(target, similarities, 10);
			for(String simi: similarities)
				data.CReateRank(Long.decode(target), Long.decode(simi), 0.0);
		}
	}
	
	
	/////////////////////////////////////////////////

	/*
	 * main function: construct graph, run pagerank, compute ranking...
	 */
	@Deprecated
	public static void main(String[] args) throws Exception {
		IData data = null;
		if (args[0].equalsIgnoreCase("real"))
			data = new RealData();
		else if (args[0].equalsIgnoreCase("simul"))
			data = new SimulatedDataOne();
		else
			throw new Exception("No data source specified");
		String[] FULLDATA = null;
		FULLDATA = data.getAllNodesIds().toArray(
				new String[data.getAllNodesIds().size()]);
		AssetRank.purge();
		Stopwatch totalTime = new Stopwatch();
		for (int j = 0; j < FULLDATA.length; j++) 
		{
			// *********if FULLDATA[i] is not an asset, target = FULLDATA[i]
			compute(FULLDATA[j],data);
			
		}
		
		totalTime.stop();
		System.out.println("Whole ranking in " + totalTime.elapsed() + "ms for "+FULLDATA.length+" items");

	}

	// pagerank computation
	public static NodeScore PageRank(
			DirectedWeightedMultigraph<String, DefaultWeightedEdge>[] graphArray,
			double damping, double personal, String user, double epsilon,
			int iters, String[] ALL_NODES) {

		double random = 1 - damping - personal;
		double sum = 0.0;
		int relation = 0;
		// initial pagerank

		double dangling = 0.0, toadd = 0;
		NodeScore pagerank, newprs;
		pagerank = new NodeScore();
		newprs = new NodeScore();
		int NODES_NUMBER = ALL_NODES.length;
		for (int i = 0; i < NODES_NUMBER; i++) {
			pagerank.addElement(ALL_NODES[i], 1.0 / NODES_NUMBER);
			newprs.addElement(ALL_NODES[i], 0.0);
		}

		NodeAction outgoing = new NodeAction();
		outgoing = GetNeighbors(graphArray, user, "outgoing");
		double neis_length = outgoing.size();

		while (iters > 0) {
			Stopwatch witers = new Stopwatch();
			iters--;
			relation = 0;
			// ======update dangling
			for (relation = 0; relation < RELATION_NUMBER; relation++) {
				if (graphArray[relation].vertexSet().size() > 1) {
					ArrayList<String> dangling_nodes = new ArrayList<String>();
					toadd = 0;
					dangling_nodes = GetDanglingNodes(graphArray[relation],ALL_NODES);
					for (int j = 0; j < dangling_nodes.size(); j++) {
						toadd += pagerank.find(dangling_nodes.get(j));
					}
					dangling += toadd * relation_weights[relation];
				}
			}
			// System.out.println("dangling before damping = " + dangling);
			dangling = (dangling * damping) / NODES_NUMBER;

			// ======finish updating dangling
			for (int i = 0; i < NODES_NUMBER; i++) {

				if (!user.equalsIgnoreCase(ALL_NODES[i])) {
					NodeAction incoming = new NodeAction();
					incoming = GetNeighbors(graphArray, ALL_NODES[i],
							"incoming");
					// System.out.println("current node = "+ALL_NODES[i]+" incoming sizes "+incoming.size());
					double newpr = 0;
					if (incoming.size() > 0) {
						double pr = 0.0;
						Set<String> neis = incoming.keySet();
						Iterator<String> it = neis.iterator();
						while (it.hasNext()) {
							String n2 = it.next();
							NodeAction n2_targets = new NodeAction();
							n2_targets = GetNeighbors(graphArray, n2,
									"outgoing");
							for (relation = 0; relation < RELATION_NUMBER; relation++) {
								if (graphArray[relation].vertexSet().size() > 1) {
									int n2_doto_n = n2_targets.find(
											ALL_NODES[i]).get(relation);
									int n2_doto_all = n2_targets
											.addActionValue(relation);
									double neis_ip = 0.0;
									if (n2_doto_all != 0) {
										neis_ip = (double) n2_doto_n
												/ (double) n2_doto_all;
									}
									pr = pr + neis_ip * pagerank.find(n2)
											* relation_weights[relation];
								}
							}
						}
						newpr = pr * damping + random / NODES_NUMBER + dangling;
					}

					if (neis_length > 0 && outgoing.find(ALL_NODES[i]) != null) {
						newpr = newpr + personal / neis_length;
					}
					newprs.updateScore(ALL_NODES[i], newpr);
				}
			}
			for (int i = 0; i < NODES_NUMBER; i++) {
				pagerank.updateScore(ALL_NODES[i], newprs.find(ALL_NODES[i]));
			}
			sum = pagerank.sumScore();
			pagerank.updateScore(user, 1 - sum);

			witers.stop();
			System.out.println("iter " + iters + " used " + witers.elapsed()
					+ " ms");
			System.out.println("user score =" + pagerank.find(user)
					+ "  sum = " + pagerank.sumScore());
		} // end of all the iterations
		System.out.println("\n end of function pagerank");
		return pagerank;
	}

	/*
	 * return the target neighbors or source neighbors of a user target
	 * neighbors: user gives actions to neighbors source neighbors: neighbors
	 * give actions to the user
	 */
	public static NodeAction GetNeighbors(
			DirectedWeightedMultigraph<String, DefaultWeightedEdge>[] graphArray,
			String user, String direct) {
		NodeAction neis = new NodeAction();
		int relation = 0;
		// System.out.println(" inside getting neighbors");
		for (relation = 0; relation < RELATION_NUMBER; relation++) {
			// System.out.println("\n -- relation -- "+relation);
			if (direct == "incoming") {
				// System.out.println("\nstart get incoming nodes per relation\n");
				// any two nodes, for any one relation, at most has one edge in
				// a direction, with weights as action counts
				if (graphArray[relation].containsVertex(user)) {
					Set<DefaultWeightedEdge> incoming_neis = graphArray[relation]
							.incomingEdgesOf(user);
					if (incoming_neis.size() > 0) {
						// System.out.println(" start get incoming neis ");
						Iterator<DefaultWeightedEdge> it = incoming_neis
								.iterator();
						while (it.hasNext()) {
							DefaultWeightedEdge edg = it.next();
							String str = graphArray[relation]
									.getEdgeSource(edg);
							int count = (int) graphArray[relation]
									.getEdgeWeight(edg);
							if (neis.find(str) != null) {
								// System.out.print(str);
								if (neis.find(str).get(relation) != 0) {
									System.out.println("\n DUPLICATED EDGE!");
									System.out.println(str + relation);
								} else {
									@SuppressWarnings("unused")
									Integer set = neis.find(str).set(relation,
											count);
								}

							} else // if neis.find(str) == null
							{
								// !!!!!!! initialize actions with EMPTY_ACTION
								ArrayList<Integer> update_action = new ArrayList<Integer>(
										Collections.nCopies(RELATION_NUMBER, 0));
								update_action.set(relation, count);
								neis.addElement(str, update_action);
							}
						}
					}
				}

			} else if (direct == "outgoing") {
				// System.out.println("\nstart get incoming nodes per relation\n");
				// any two nodes, for any one relation, at most has one edge in
				// a direction, with weights as action counts
				if (graphArray[relation].containsVertex(user)) {
					Set<DefaultWeightedEdge> outgoing_neis = graphArray[relation]
							.outgoingEdgesOf(user);
					// System.out.println(" outgoing neis size = "+outgoing_neis.size());
					if (outgoing_neis.size() > 0) {
						// System.out.println(user + " has outgoing neighbors");
						Iterator<DefaultWeightedEdge> it = outgoing_neis
								.iterator();
						while (it.hasNext()) {
							DefaultWeightedEdge edg = it.next();
							String str = graphArray[relation]
									.getEdgeTarget(edg);
							int count = (int) graphArray[relation]
									.getEdgeWeight(edg);
							if (neis.find(str) != null) {
								// System.out.print(str);
								if (neis.find(str).get(relation) != 0) {
									System.out.println("\n DUPLICATED EDGE!");
									System.out.println(str + relation);
								} else {
									@SuppressWarnings("unused")
									Integer set = neis.find(str).set(relation,
											count);
								}

							} else // if neis.find(str) == null
							{
								// !!!!!!! initialize actions with EMPTY_ACTION
								ArrayList<Integer> update_action = new ArrayList<Integer>(
										Collections.nCopies(RELATION_NUMBER, 0));
								update_action.set(relation, count);
								neis.addElement(str, update_action);
							}
						}
					}
				}

			}

			// if the input direction is neither incoming or outgoing
			else {
				System.out.println("direct error");
			}
		}
		// System.out.println("---neis---");
		// System.out.print(neis);
		return neis;

	}

	// return dangling nodes for each relation <nodes with no outgoing links>
	public static ArrayList<String> GetDanglingNodes(
			DirectedWeightedMultigraph<String, DefaultWeightedEdge> g, String[] ALL_NODES) {
		ArrayList<String> dangling = new ArrayList<String>();		
		if (g.vertexSet().size() > 1) {
			int NODES_NUMBER = ALL_NODES.length;
			for (int i = 0; i < NODES_NUMBER; i++) {
				String str = ALL_NODES[i];
				if (g.containsVertex(str)) {
					if (g.outDegreeOf(str) == 0) // and dangling.index(str)
					{
						dangling.add(str);
					}
				} else {
					dangling.add(str);
				}
			}
		} else {
			System.out.println("no such relation");
		}
		return dangling;
	}

	// return lonely nodes, considering all relations.
	public static ArrayList<String> GetLonelyNodes(
			DirectedWeightedMultigraph<String, DefaultWeightedEdge>[] graphArray,String[] ALL_NODES) {
		ArrayList<String> lonelynodes = new ArrayList<String>();
		int NODES_NUMBER = ALL_NODES.length;
		for (int i = 1; i < NODES_NUMBER; i++) {
			int flag = 0;
			for (int relation = 0; relation < RELATION_NUMBER; relation++) {
				if (graphArray[relation].containsVertex(ALL_NODES[i])) {
					flag = 1;
					break;
				}
			}
			if (flag == 0) {
				lonelynodes.add(ALL_NODES[i]);
			}

		}
		return lonelynodes;
	}

	// construct graph from database
	@SuppressWarnings("unchecked")
	public static DirectedWeightedMultigraph<String, DefaultWeightedEdge>[] GraphConstruct(
			String user, IData data, ArrayList<String> ARRAY_NODES) {
		DirectedWeightedMultigraph<String, DefaultWeightedEdge>[] graphArray;
		graphArray = new DirectedWeightedMultigraph[RELATION_NUMBER];
		Stopwatch wrelation = new Stopwatch();
		for (int relation = 0; relation < RELATION_NUMBER; relation++) {
			wrelation.start();
			System.out.println("\n");
			System.out.print(relation);
			graphArray[relation] = GraphRelation(relation, user, data, ARRAY_NODES);
			wrelation.stop();
			System.out.println(" this relation takes " + wrelation.elapsed()
					+ "ms");

		}
		return graphArray;

	}

	private static DirectedWeightedMultigraph<String, DefaultWeightedEdge> constructRelationGraph(
			DirectedWeightedMultigraph<String, DefaultWeightedEdge> wg,
			String rel, String user, IData datas,ArrayList<String> ARRAY_NODES) {
		System.out.println("Construct " + rel + " Graph");
		// fetch all space record from database, a space belong to an actor
		List<IRelation> relations = datas.findAllInRelation(rel, user);
		// -------------- scale for efficiency test ------------------------
		for (IRelation relation : relations) {
			if (wg.containsEdge(relation.getSource().getStrId(), relation
					.getTarget().getStrId())) {
				System.out.println("duplicated " + rel + " record !");
			} else {
				String source = relation.getSource().getStrId();
				String destination = relation.getTarget().getStrId();
				if (ARRAY_NODES.contains(source)
						&& ARRAY_NODES.contains(destination)) {
					if (!wg.containsVertex(relation.getSource().getStrId()))
						wg.addVertex(relation.getSource().getStrId());
					if (!wg.containsVertex(relation.getTarget().getStrId()))
						wg.addVertex(relation.getTarget().getStrId());
					wg.addEdge(relation.getSource().getStrId(), relation
							.getTarget().getStrId());
				}
			}
		}
		return wg;
	}

	//
	public static DirectedWeightedMultigraph<String, DefaultWeightedEdge> GraphRelation(
			int relation, String user, IData datas, ArrayList<String> ARRAY_NODES) {
		DirectedWeightedMultigraph<String, DefaultWeightedEdge> weightedGraph;
		weightedGraph = new DirectedWeightedMultigraph<String, DefaultWeightedEdge>(
				DefaultWeightedEdge.class);
		switch (relation) {
		case 0: // construct belong graph - space has many assets (space,
			// actors, assets)
			return constructRelationGraph(weightedGraph, "belong", user, datas, ARRAY_NODES);
		case 1: // construct similar graph
			System.out.println("\nConstruct similar Graph");
			ArrayList<ISimilarity> similarities = datas.getAllSimilarities();
			for (ISimilarity similarity : similarities) {
				String source = similarity.getSource().getStrId();
				String destination = similarity.getTarget().getStrId();
				if (ARRAY_NODES.contains(source)
						&& ARRAY_NODES.contains(destination)) {
					if (!weightedGraph.containsEdge(similarity.getSource()
							.getStrId(), similarity.getTarget().getStrId())) {
						if (!weightedGraph.containsVertex(similarity
								.getSource().getStrId()))
							weightedGraph.addVertex(similarity.getSource()
									.getStrId());
						if (!weightedGraph.containsVertex(similarity
								.getTarget().getStrId()))
							weightedGraph.addVertex(similarity.getTarget()
									.getStrId());
						weightedGraph.addEdge(
								similarity.getSource().getStrId(), similarity
										.getTarget().getStrId());
					}
				}
			}
			return (weightedGraph);
		default: // return emppty graph
			System.out.println("\nNo Such Relation, return Empty Graph");
			return (weightedGraph);
		}

	}

	// construct a directed weighted graph, each graph is based on one relation,
	// using artifitial data
	public static DirectedWeightedMultigraph<String, DefaultWeightedEdge> TestGraphConstruct(
			int relation) {
		DirectedWeightedMultigraph<String, DefaultWeightedEdge> weightedGraph;
		weightedGraph = new DirectedWeightedMultigraph<String, DefaultWeightedEdge>(
				DefaultWeightedEdge.class);
		// for relations [1: visit 2: belong 3: membership 4: comment]
		// for each relation, go through all the edges.
		switch (relation) {
		case 0: // construct visit graph
			System.out.println("\nConstruct Visit Graph");
			// fetch all visit record from database
			// for each visit record
			weightedGraph.addVertex("actor1");
			weightedGraph.addVertex("actor2");
			weightedGraph.addVertex("asset1");
			weightedGraph.addVertex("asset2");
			weightedGraph.setEdgeWeight(
					weightedGraph.addEdge("actor1", "actor2"), 2);
			weightedGraph.setEdgeWeight(
					weightedGraph.addEdge("actor2", "asset1"), 5);
			weightedGraph.setEdgeWeight(
					weightedGraph.addEdge("actor1", "asset2"), 8);
			return (weightedGraph);
		case 1: // construct belong graph - an asset belongs to one or many
				// spaces, spaces deliver interest to assets
			System.out.println("\nConstruct Belong Graph");
			// fetch all space record from database, a space belong to an actor
			// for each belong record, in fact it is has, space 1 has asset 1
			weightedGraph.addVertex("asset1");
			weightedGraph.addVertex("asset2");
			weightedGraph.addVertex("space1");
			weightedGraph.addEdge("space1", "asset1");
			weightedGraph.addEdge("space1", "asset2");
			return (weightedGraph);
		case 2: // construct membership graph: an actor is a member of a space
			System.out.println("\nConstruct Membership Graph");
			weightedGraph.addVertex("actor1");
			weightedGraph.addVertex("actor2");
			weightedGraph.addVertex("space2");
			weightedGraph.addVertex("space1");
			weightedGraph.addEdge("actor1", "space2");
			weightedGraph.addEdge("actor2", "space1");
			return (weightedGraph);
		case 3: // construct comment graph: an actor comments a space/asset...
			System.out.println("\nConstruct Comment Graph");
			weightedGraph.addVertex("actor2");
			weightedGraph.addVertex("space2");
			weightedGraph.addEdge("actor2", "space2");
			return (weightedGraph);
		default: // return emppty graph
			System.out.println("\nNo Such Relation, return Empty Graph");
			return (weightedGraph);

		}

	}

	// to be deleted
	public static void PageRankPre(double damping,
			DirectedWeightedMultigraph<String, DefaultWeightedEdge>[] graphArray, String[] ALL_NODES) {
		double dangling = 0.0, toadd = 0;
		NodeScore pagerank, newprs;
		pagerank = new NodeScore();
		newprs = new NodeScore();
		int NODES_NUMBER = ALL_NODES.length;
		for (int i = 0; i < NODES_NUMBER; i++) {
			pagerank.addElement(ALL_NODES[i], 1.0 / NODES_NUMBER);
			newprs.addElement(ALL_NODES[i], 0.0);
		}
		// generate dangling value
		// initialize pagerank, each has an equal score -- equal chance to be
		int relation = 0;
		System.out.println("\n----Start get dangling nodes-----\n");
		Stopwatch w = new Stopwatch();
		for (relation = 0; relation < RELATION_NUMBER; relation++) {
			System.out.println(relation);
			if (graphArray[relation].vertexSet().size() > 1) {
				ArrayList<String> dangling_nodes = new ArrayList<String>();
				toadd = 0;
				dangling_nodes = GetDanglingNodes(graphArray[relation],ALL_NODES);
				System.out.println("in dangling " + relation
						+ " the nodes are " + dangling_nodes);
				for (int j = 0; j < dangling_nodes.size(); j++) {
					toadd += pagerank.find(dangling_nodes.get(j));
				}
				dangling += toadd * relation_weights[relation];
			}

		}
		dangling = (dangling * damping) / NODES_NUMBER;
		System.out.println("dangling = " + dangling);
		w.stop();
		System.out.println("-------dangling used " + w.elapsed()
				+ "ms---------");

		// return dangling, pagerank, newprs

	}

}